package leetcode;

import util.LinkList;
import util.ListNode;

/**
 * @Project : algorithm-learning-java
 * @Package : leetcode
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/1/19 10:19
 */
public class Q0086 {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        ListNode h = new ListNode(-0x3f3f3f3f, head);
        ListNode p = h;
        while (p.next != null && p.next.val < x) {
            p = p.next;
        }
        if (p.next == null) return head;
        ListNode spre = p.next;
        ListNode s = spre.next;
        while (s != null) {
            if (s.val >= x) {
                spre = s;
                s = s.next;
            } else {
                spre.next = s.next;
                s.next = p.next;
                p.next = s;
                p = p.next;
                s = spre.next;
            }
        }
        return h.next;
    }

    public static void main(String[] args) {
        Q0086 sl = new Q0086();
        int[] head = {1, 4, 3, 2, 5, 2};
        int x = 3;
        ListNode h = LinkList.createList(head);
        LinkList.printList(sl.partition(h, x));
    }
}
